"""
二分搜索算法
假定数组a是已按从小到大的顺序拍好

快速排序
输入 a，0，len(a)-1
输出排好序a
"""

import random as rd


def BinarySearch(a, x, n):
    l = 0
    r = n - 1
    while l <= r:
        mid = int((l + r) / 2)
        if a[mid] == x:
            return mid
        elif a[mid] > x:
            r = mid - 1
        elif a[mid] < x:
            l = mid + 1

    return -1


# 数组a，选p为基准，进行分解，小的左边，大的去右边
def Partition(a, p: int, r: int):
    j = r
    i = p + 1
    x = a[p]
    while True:
        while a[i] <= x and i < r:  # a[i]<=x   左边，第一次停在a[i]>x处
            i = i + 1
        while a[j] >= x and j > p:  # a[j]>=x   右边，第一次停在a[j]<x处
            j = j - 1
        if i >= j:  # 这时如果i>=j,说明数组已经分成左右两块
            break
        a[i], a[j] = a[j], a[i]
    a[p] = a[j]
    a[j] = x
    # print(a)
    return j


def QuickSort(a, p, r):
    if p < r:
        q = Partition(a, p, r)
        QuickSort(a, p, q)
        QuickSort(a, q + 1, r)


# 随机选取基准，改进算法
def RandomizedPartiton(a, p, r):
    i = rd.randint(p, r)
    a[i], a[p] = a[p], a[i]
    return Partition(a, p, r)


def RandomizedQuickSort(a, p, r):
    if p < r:
        q = RandomizedPartiton(a, p, r)
        RandomizedQuickSort(a, p, q)
        RandomizedQuickSort(a, q + 1, r)
